package com.skh.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * created by skh on 2019/6/18
 */
public class TwoSum {

	/*
	给定一个整数数组，找到两个数字，使它们加起来等于一个特定的目标数字。
	函数twoSum应该返回这两个数字的索引，使它们之和等于目标，其中index1必须小于index2。请注意，您返回的答案(index1和index2)都不是从零开始的。
	您可以假设每个输入都只有一个解。
	Input: numbers={2, 7, 11, 15}, target=9
	Output: index1=1, index2=2
	 */

	/*
	思路
	    //map里面放 键为target-每个数的结果 值为下标
        //每次放入的时候看是否包含 当前值
        //有的话说明当前值和已包含的值下标的那个元素为需要的结果
	 */
	public int[] twoSum(int[] numbers, int target) {
		int[] result = new int[2];
		int length = numbers.length;
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < length; i++) {
			if (map.containsKey(numbers[i])) {
				result[0] = map.get(numbers[i])+1;
				result[1] = i+1;
				break;
			}else {
				map.put(target-numbers[i],i);
			}
		}
		return  result;
	}
}
